package algorithm.backtracing;

import util.GsonUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 51. N-Queens
 * leetcode : https://leetcode.com/problems/n-queens
 * Difficulty : Hard
 *
 * N皇后问题，要求不止得求出有几个结果，还要把所有结果集都返回
 *
 * @Author Antony
 * @Since 2018/11/15 16:35
 */
public class NQueens {

    public static void main(String[] args) {
        List<List<String>> nQueens = solveNQueens(5);
        System.out.println(GsonUtil.toJson(nQueens));
        printNQueens(nQueens);
    }

    private static void printNQueens(List<List<String>> nQueens){
        System.out.println(String.format("有%s个结果",nQueens.size()));
        for(List<String> list : nQueens){
            for(String line : list){
                line.chars().forEach(c -> System.out.print("[" + (char)c + "]"));
                System.out.println();
            }
            System.out.println("---");
        }
    }


    /**
     * leetcode : 4ms - beats 91.99%
     * @param n
     * @return
     */
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        int[][] cheese = new int[n][n];
        for(int i=0; i<n/2; i++){
            backtrack(cheese, result, 0, i, true);
        }
        if(n%2 == 1){
            backtrack(cheese, result, 0, n/2, false);
        }
        return result;
    }

    /**
     *
     * @param cheese
     * @param result
     * @param y
     * @param x
     * @param image 是否有镜像结果。有的话，在找到结果时，会同时将结果和镜像结果都加到result中
     */
    private static void backtrack(int[][] cheese, List<List<String>> result, int y, int x, boolean image){
        cheese[y][x] = 1;
        if(y == cheese.length-1){
            addResult(cheese, result, image);
        }else{
            for(int i=0; i<cheese[0].length; i++){
                if(checkPosition(cheese, y+1, i)){
                    backtrack(cheese, result, y+1, i, image);
                }
            }
        }
        cheese[y][x] = 0;
    }

    private static void addResult(int[][] cheese, List<List<String>> result, boolean image){
        List<String> list = new ArrayList<>(cheese.length);
        List<String> imageList = null;
        if(image){
            imageList = new ArrayList<>(cheese.length);
        }
        for(int i=0; i<cheese.length; i++){
            StringBuilder bu = new StringBuilder();
            for(int j=0; j<cheese[0].length; j++){
                if(cheese[i][j] == 1){
                    bu.append("Q");
                }else{
                    bu.append(".");
                }
            }
            list.add(bu.toString());
            if(image){
                imageList.add(bu.reverse().toString());
            }
        }
        result.add(list);
        if(image){
            result.add(imageList);
        }
    }


    private static boolean checkPosition(int[][] cheese, int y, int x){
        int left=x, right=x;
        int len = cheese[0].length;
        boolean leftCheck, rightCheck, upCheck, result;
        for(int i=y-1; i>=0; i--){
            left -= 1;
            right +=1;
            leftCheck = left<0 ? true : cheese[i][left]==0;
            rightCheck = right>=len ? true : cheese[i][right]==0;
            upCheck = cheese[i][x]==0;
            result = leftCheck && rightCheck && upCheck;
            if(!result){
                return false;
            }
        }
        return true;
    }
}
